#include <vector>
#include <string>
#include <tuple>
using namespace std;

class Solution
{
public:
    pair<int, int> expand(string& s, int len, int l, int r)
    {
        while(l >= 0 && r < len && s[l] == s[r])
        {
            l --;
            r ++;
        }

        return {l + 1, r - 1};
    }

    string longestPalindrome(string s)
    {
        if(s.size() == 1)
        {
            return s;
        }

        int len = 0, left, right, n = s.length();
        for(int i = 0; i < n; i ++)
        {
            int l1, r1, l2, r2;
            tie(l1, r1) = expand(s, n, i, i);
            tie(l2, r2) = expand(s, n, i, i + 1);
            if(len < r1 - l1 + 1)
            {
                len = r1 - l1 + 1;
                left = l1;
                right = r1;
            }
            if(len < r2 - l2 + 1)
            {
                len = r2 - l2 + 1;
                right = r2;
                left = l2;
            }
        }

        return s.substr(left, right - left + 1);
    }
};
